package BinaryTree;

public class ValidBinarySearchTree_98 {

    /**
     * 判定是否二叉搜索树
     * curr当前节点
     * 1. 左子树是否合格 max min
     * 2. 右子树是否合格 max min
     * 3. 左右合格，并且curr.val > left.max, curr.val<right.min.
     * **/
    public boolean isValidBST(TreeNode root) {
        return validBST(root).isBST;
    }

    private Info validBST(TreeNode node) {
        if (node == null) return null;
//        if(node==null) return new Info(true, Integer.MIN_VALUE, Integer.MAX_VALUE); 如果val范围小于int最大值

        Info left = validBST(node.left);
        Info right = validBST(node.right);
        int max = node.val;
        int min = node.val;
        int size = 1;
        if (left != null) {
            max = Math.max(max, left.max);
            min = Math.min(min, left.min);
            size += left.size;
        }
        if (right != null) {
            max = Math.max(max, right.max);
            min = Math.min(min, right.min);
            size += right.size;
        }

        // int max = Math.max(node.val, Math.max(right==null?node.val:right.max, left==null?0:left.max));
        // int min = Math.min(node.val, Math.min(right==null?0:right.min, left==null?0:left.min));
        // System.out.println(node.val + " " + left.max+ " "+ right.min);
        // System.out.println((left==null?true:node.val>left.max) && (right==null?true:node.val<right.min));

        boolean isBST = (left == null ? true : left.isBST) && (right == null ? true : right.isBST)
                && (left == null ? true : (node.val > left.max)) && (right == null ? true : (node.val < right.min));
        // System.out.println(node.val + " " + isBST+ " "+ max + " "+ min);
        return new Info(isBST, max, min, size);
    }

    class Info {
        public int max;
        public int min;
        public boolean isBST;
        public int size;

        public Info(boolean is, int ma, int mi, int si) {
            isBST = is;
            max = ma;
            min = mi;
            size = si;
        }
    }
}
